//给你一个整数 n 表示一棵 满二叉树 里面节点的数目，节点编号从 1 到 n 。根节点编号为 1 ，树中每个非叶子节点 i 都有两个孩子，分别是左孩子 2 
//* i 和右孩子 2 * i + 1 。 
//
// 树中每个节点都有一个值，用下标从 0 开始、长度为 n 的整数数组 cost 表示，其中 cost[i] 是第 i + 1 个节点的值。每次操作，你可以将
//树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。 
//
// 你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。 
//
// 注意： 
//
// 
// 满二叉树 指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个子节点，且所有叶子节点距离根节点距离相同。 
// 路径值 指的是路径上所有节点的值之和。 
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：n = 7, cost = [1,5,2,2,3,3,1]
//输出：6
//解释：我们执行以下的增加操作：
//- 将节点 4 的值增加一次。
//- 将节点 3 的值增加三次。
//- 将节点 7 的值增加两次。
//从根到叶子的每一条路径值都为 9 。
//总共增加次数为 1 + 3 + 2 = 6 。
//这是最小的答案。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：n = 3, cost = [5,3,3]
//输出：0
//解释：两条路径已经有相等的路径值，所以不需要执行任何增加操作。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= n <= 10⁵ 
// n + 1 是 2 的幂 
// cost.length == n 
// 1 <= cost[i] <= 10⁴ 
// 
//
// Related Topics 贪心 树 数组 动态规划 二叉树 👍 54 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MakeCostsOfPathsEqualInABinaryTree {
    public static void main(String[] args) {
        Solution solution = new MakeCostsOfPathsEqualInABinaryTree().new Solution();
        System.out.println(solution.minIncrements(15, new int[]{764, 1460, 2664, 764, 2725, 4556, 5305, 8829, 5064, 5929, 7660, 6321, 4830, 7055, 3761}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minIncrements(int n, int[] cost) {
//
//            int index = 1;
//            int res = 0;
//            int point = 0;
//            int row = 0;
//
//            int[] arr = new int[n];
//            Arrays.fill(arr, Integer.MIN_VALUE);
//
//            while (point < cost.length) {
//                int step = 0;
//                for (int i = point; i < point+index; i++,step++) {
//                    arr[row] = Math.max(arr[row], cost[i]);
//                }
//                row++;
//                point += step;
//                index = index << 1;
//            }
//
//            //reset
//            index = 1;
//            res = 0;
//            point = 0;
//            row = 0;
//
//            while (point < cost.length) {
//                int step = 0;
//                for (int i = point; i < point+index; i++,step++) {
//                    int cal = arr[row]-cost[i];
//                    res += cal;
//                }
//                row++;
//                point += step;
//                index = index << 1;
//            }
//            return res;
            int ans = 0;
            for (int i = n / 2; i > 0; i--) { // 从最后一个非叶节点开始算
                ans += Math.abs(cost[i * 2 - 1] - cost[i * 2]); // 两个子节点变成一样的
                cost[i - 1] += Math.max(cost[i * 2 - 1], cost[i * 2]); // 累加路径和
            }
            return ans;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}